#include "BTreeNode.h"

#define LEAF_ENTRY_SIZE 12
#define NON_LEAF_ENTRY_SIZE 8
#define NON_LEAF_BYTES_RESERVED 12
#define LEAF_ENTRY_MAX 83
//#define LEAF_ENTRY_MAX 3 // For testing purposes
#define LEAF_CODE -999
#define LEAF_END -999
#define RECORD_ID_SIZE 8
#define OFFSET_KEY_COUNT 0
#define OFFSET_LEAF_CODE 0
#define OFFSET_ROOT_PID 4
#define OFFSET_TREE_HEIGHT 8
#define OFFSET_RID_PID 0
#define OFFSET_RID_SID 4
#define OFFSET_KEY 8

using namespace std;

/////////////////////////////////////////////////////////////////////
// Leaf Node
//  - The first 12 bytes represent the following:
//	- (leaf, rootPid, treeHeight)
/////////////////////////////////////////////////////////////////////

/*
 * Constructor to initialize each byte in buffer to '-' initially to be
 * able to implement the getKeyCount() function
 */
BTLeafNode::BTLeafNode()
{
	memset(buffer, '-', PageFile::PAGE_SIZE); // Set buffer to be used by getKeyCount()
	int leafCode = LEAF_CODE;
	memcpy(&(buffer[OFFSET_LEAF_CODE]), &leafCode, sizeof(int));
	setNextNodePtr(LEAF_END);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	memset(buffer, '-', PageFile::PAGE_SIZE); // Set buffer to be used by getKeyCount()
	int leafCode = LEAF_CODE;
	//memcpy(&(buffer[OFFSET_LEAF_CODE]), &leafCode, sizeof(int));
	//setNextNodePtr(LEAF_END);
	//pf.write(pid, buffer);
	currentPid = pid; // Set the currentPid to where the contents of the node is stored
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	currentPid = pid; // Set the currentPid to where the contents of the node is stored
	return pf.write(pid, buffer);
}

/*
 * Each node, the PageFile class, has entries that consist of RecordId and key.
 * The size of RecordId is 8 bytes because RecordId is made up of PageId(4 bytes)
 * and int(4 bytes).  The key is also and int(4 bytes), so each entry in the
 * PageFile is 12 bytes.  There is an exception that the last 4 bytes is reserved
 * for PageId, which points the next leaf node.
 * /

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int numKeys = 0; // Initially set number of keys to 0
	int entrySize = LEAF_ENTRY_SIZE; // Size of each entry in bytes
	
	// Size of node excluding the PageId at the end
	int nodeSize = PageFile::PAGE_SIZE - sizeof(PageId) - LEAF_ENTRY_SIZE;
	
	for (int entry = entrySize; entry < nodeSize ; entry += entrySize )
	{
		// Check the lowest byte of an int
		if (buffer[entry+3] != '-')
		{
			numKeys++; // PageId in RecordId has been set, an entry exists
		}
		else
		{
			break;
		}
	}
	
	return numKeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int keyCount = getKeyCount();
	
	//Size of node excluding the PageId at the end
	int nodeSize = PageFile::PAGE_SIZE - sizeof(PageId) - LEAF_ENTRY_SIZE;
	
	// Check whether node is full
	if (keyCount >= LEAF_ENTRY_MAX)
	{
		return RC_NODE_FULL; // Node is already full
	}
	
	int insertIndex;
	
	// Use locate() to find index to insert input
	RC success = locate(key, insertIndex);
	
	// Check if locate returned an error
	if (success != 0)
	{
		insertIndex = keyCount; // The key is the largest in the node
	}
	
	insertIndex++;
	
	// Move the entries in buffer by one entry to the right
	memmove(&(buffer[(insertIndex*LEAF_ENTRY_SIZE)+LEAF_ENTRY_SIZE]),
					&(buffer[(insertIndex*LEAF_ENTRY_SIZE)]), nodeSize-((insertIndex+1)*LEAF_ENTRY_SIZE));

	// Insert the new entry
	memcpy(&(buffer[(insertIndex*LEAF_ENTRY_SIZE)+OFFSET_RID_PID]), &(rid.pid),
				 sizeof(PageId));
	memcpy(&(buffer[(insertIndex*LEAF_ENTRY_SIZE)+OFFSET_RID_SID]), &(rid.sid),
				 sizeof(int));
	memcpy(&(buffer[(insertIndex*LEAF_ENTRY_SIZE)+OFFSET_KEY]), &key, sizeof(int));
	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int keyCount = getKeyCount();
	
	// Check if node is full
	if (keyCount < LEAF_ENTRY_MAX)
	{
		return RC_INVALID_FILE_FORMAT; // The node is not full
	}
	
	// Get the last id of last entry before split
	int splitId = LEAF_ENTRY_MAX / 2 + 1;
	
	for (int i = splitId; i < LEAF_ENTRY_MAX; i++)
	{
		RecordId insertRid;
		int insertKey;
		
		memcpy(&(insertRid.pid), &(buffer[((i+1)*LEAF_ENTRY_SIZE)+OFFSET_RID_PID]),
					 sizeof(PageId));
		memcpy(&(insertRid.sid), &(buffer[((i+1)*LEAF_ENTRY_SIZE)+OFFSET_RID_SID]),
					 sizeof(int));
		memcpy(&insertKey, &(buffer[((i+1)*LEAF_ENTRY_SIZE)+OFFSET_KEY]), sizeof(int));
		
		// Move over the entries right of the split index to the sibling node
		sibling.insert(insertKey, insertRid);
		
		// Get the key value of the first entry of sibling node
		if (i == splitId)
		{
			siblingKey = insertKey;
		}
		
		// Clear the data of the moved over entry
		memset(&(buffer[((i+1)*LEAF_ENTRY_SIZE)]), '-',
						 LEAF_ENTRY_SIZE); // Set buffer to be used by getKeyCount()
	}
	
	// Set sibling's next pointer
	sibling.setNextNodePtr(getNextNodePtr());
	
	// Set current node's next pointer
	setNextNodePtr(sibling.retCurrentPid());
	
	// Insert the new entry into node
	if (key < siblingKey)
	{
		insert(key, rid);
	}
	else
	{
		sibling.insert(key, rid);
	}
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int keyCount = getKeyCount();
	
	int i;
	for (i = 0; i < keyCount; i++)
	{
		int curKey;
		memcpy(&curKey, &(buffer[((i+1)*LEAF_ENTRY_SIZE)+RECORD_ID_SIZE]), sizeof(int));
		
		if (searchKey <= curKey)
		{
			eid = i;
			return 0;
		}
	}
	
	return RC_NO_SUCH_RECORD; // No such record was found
	
	/*
	if (i <= LEAF_ENTRY_MAX)
	{
		eid = i;
		return 0;
	}
	else
	{
		return RC_NO_SUCH_RECORD; // No such record was found
	}
	*/
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	if (eid < 0 || eid > (getKeyCount()-1))
	{
		return RC_INVALID_CURSOR; // not a valid eid
	}
	
	int entrySize = LEAF_ENTRY_SIZE; // Size of each entry in bytes
	int entryIndex = eid * entrySize; // Starting index in buffer where
																		// information is stored
	
	// Read the values into the proper variables
	memcpy(&rid.pid, &(buffer[entryIndex+entrySize+OFFSET_RID_PID]), sizeof(PageId));
	memcpy(&rid.sid, &(buffer[entryIndex+entrySize+OFFSET_RID_SID]), sizeof(int));
	memcpy(&key, &(buffer[entryIndex+entrySize+OFFSET_KEY]), sizeof(int));
	
	return 0;
}

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	// Index of where the pid of next sibling node starts
	int pidIndex = PageFile::PAGE_SIZE - sizeof(PageId);
	
	PageId nextNode; // Store next node's pid
	memcpy(&nextNode, &(buffer[pidIndex]), sizeof(PageId)); // Read value from buffer
	
	// Return the next node pointer
	return nextNode;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	if (pid < 0 && pid != LEAF_END)
	{
		return RC_INVALID_PID; // Invalid pid
	}
	
	// Index of where the pid of next sibling node starts
	int pidIndex = PageFile::PAGE_SIZE - sizeof(PageId);
	
	memcpy(&(buffer[pidIndex]), &pid, sizeof(PageId));
	
	return 0;
}

/*
 * Sets the currentPid
 * @param pid[IN] the pid to set currentPid to
 * @return 0 if successful.
 */
RC BTLeafNode::setCurrentPid(PageId pid)
{
	currentPid = pid;
	return 0;
}

/*
 * @return the pid of the current node.
 */
PageId BTLeafNode::retCurrentPid()
{
	return currentPid;
}

/*
 * Set parameters for the current node
 * @param rootPid[IN] set the rootPid of the tree
 * @param treeHeight[IN] set the treeHeight of the tree
 * @return 0 if successful.
 */
RC BTLeafNode::setParameters(int rootPid, int treeHeight)
{
	int leafCode = LEAF_CODE;
	memcpy(&(buffer[OFFSET_LEAF_CODE]), &leafCode, sizeof(int));
	memcpy(&(buffer[OFFSET_ROOT_PID]), &rootPid, sizeof(int));
	memcpy(&(buffer[OFFSET_TREE_HEIGHT]), &treeHeight, sizeof(int));
	
	return 0;
}

/////////////////////////////////////////////////////////////////////
// Non-Leaf Node
//  - The first 12 bytes represent the following:
//	- (size, rootPid, treeHeight)
/////////////////////////////////////////////////////////////////////

/*
 * Constructor to initialize each the first 4 bytes to the number of
 * keys the node contains
 */
BTNonLeafNode::BTNonLeafNode()
{
	int initKeyCount = 0;
	memcpy(&(buffer[OFFSET_KEY_COUNT]), &initKeyCount, sizeof(int));
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * The layout of the non-leaf nodes are as follows:
 * The first 4 bytes are going to store how many key
 * values the node has.  Then it would have 128 PageIds
 * and 127 key values.

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int keyIndex = 0; // Set to 0 initially
	
	// The first 4 bytes represent the key count
	memcpy(&keyIndex, &buffer, sizeof(int));
	
	return keyIndex;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	// Check if the node is already full
	int pairSize = sizeof(int) + sizeof(PageId); // Size of key and pid pair
	int KEY_MAX = PageFile::PAGE_SIZE/pairSize-2;
	int keyCount = getKeyCount();
	
	// Testing
	//KEY_MAX = 3;
	//printf("KEYMAX: %d\n", keyCount);
	
	if (keyCount >= KEY_MAX)
	{
		return RC_NODE_FULL;  // The node is already full
	}
	
	int i; // Stores the index to insert new entry
	for (i = 0; i < keyCount; i++)
	{
		int curKey;
		memcpy(&curKey, &(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4)]), sizeof(int));
		
		if (key <= curKey)
		{
			break;
		}
	}
	
	memmove(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+pairSize+4)]),
					&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4)]),
					PageFile::PAGE_SIZE-(i*pairSize)-NON_LEAF_BYTES_RESERVED-2*pairSize);
	
	memcpy(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4)]), &key, sizeof(int));
	
	memcpy(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4+4)]), &pid, sizeof(PageId));
	
	/*
	// Move the entries in buffer by one entry to the right
	//memmove(&(buffer[i*pairSize+NON_LEAF_BYTES_RESERVED+pairSize]),
	//				&(buffer[i*pairSize+NON_LEAF_BYTES_RESERVED]),
	//				PageFile::PAGE_SIZE-(i*pairSize)-NON_LEAF_BYTES_RESERVED-pairSize);
	memmove(&(buffer[i*pairSize+NON_LEAF_BYTES_RESERVED+pairSize+4]),
					&(buffer[i*pairSize+NON_LEAF_BYTES_RESERVED+4]),
					PageFile::PAGE_SIZE-(i*pairSize)-NON_LEAF_BYTES_RESERVED-pairSize-4);
	
	// Insert new entry
	//memcpy(&(buffer[(i*pairSize+countOffset)]), &pid, sizeof(PageId));
	memcpy(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4)]), &key, sizeof(int));
	// Two below added
	
	// Might neeed
	//memcpy(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED)]),
	//			 &(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+8)]), sizeof(PageId));
				 
	memcpy(&(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+8)]), &pid, sizeof(PageId));
	*/
	
	// Update entry count, first 4 bytes store the count
	int newCount = getKeyCount();
	newCount++;
	memcpy(&(buffer[OFFSET_KEY_COUNT]), &newCount, sizeof(int));
	
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int pairSize = sizeof(int) + sizeof(PageId); // Size of key and pid pair
	int keyCount = getKeyCount();
	
	// Get the last id of last entry before split
	int medianId = keyCount / 2;
	
	// Decrement the count of keys
	int newCount = getKeyCount();
	newCount--;
	memcpy(&(buffer[OFFSET_KEY_COUNT]), &newCount, sizeof(int));
	
	// Set the value of midKey
	memcpy(&midKey, &(buffer[(medianId*pairSize+NON_LEAF_BYTES_RESERVED+4)]),
				 sizeof(int));
	
	for (int i = medianId+1; i < keyCount; i++)
	{
		int insertPid;
		int insertKey;
		
		memcpy(&insertPid, &(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED+4)]),
					 sizeof(PageId));
		memcpy(&insertKey, &(buffer[(i*pairSize+NON_LEAF_BYTES_RESERVED)]),
					 sizeof(int));
		
		// Move over the entries right of the split index to the sibling node
		RC status = sibling.insert(insertKey, insertPid);
		
		// Error checking for insert
		if (status != 0)
		{
			return status;
		}
		
		// Decrement the count of keys
		newCount = getKeyCount();
		newCount--;
		memcpy(&(buffer[OFFSET_KEY_COUNT]), &newCount, sizeof(int));
	}
	
	// Insert the new key entry
	if (key < medianId)
	{
		RC status = insert(key, pid);
		
		// Error checking for insert
		if (status != 0)
		{
			return status; // Insert failed
		}
	}
	else
	{
		RC status = sibling.insert(key, pid);
		
		// Error checking for insert
		if (status != 0)
		{
			return status; // Insert failed
		}
	}
	
	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	for (int i = 0; i < getKeyCount(); i++)
	{
		// Get the key value at current location
		int keyValue = 0; // Set to 0 initially
	
		// Bytes 4-8 represent key value
		memcpy(&keyValue, &(buffer[(i*NON_LEAF_ENTRY_SIZE)+8+8]), sizeof(int));
		
		if (searchKey < keyValue)
		{
			// Get the pid
			memcpy(&pid, &(buffer[(i*NON_LEAF_ENTRY_SIZE)+8+4]),
						 sizeof(PageId));
			break; // Found pid, so break out of loop
		}
		//else if ((i*nonLeafEntrySize+8+4) == ((getKeyCount()-1)*
		//					nonLeafEntrySize + sizeof(PageId)))
		else if (i == getKeyCount()-1)
		{
			// Special case where key is greater than last key
			// Get the pid
			memcpy(&pid, &(buffer[(i*NON_LEAF_ENTRY_SIZE)+8+12]), sizeof(PageId));
		}
	}
	
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	// Put the current key count to the first 4 bytes
	int curKeyCount = 1;
	memcpy(&(buffer[OFFSET_KEY_COUNT]), &curKeyCount, sizeof(int));
	
	// The next 8 bytes reserved for rootPid and treeHeight
	int treeHeight;
	//int rootPid;
	memcpy(&treeHeight, &(buffer[OFFSET_TREE_HEIGHT]), sizeof(int));
	treeHeight++;
	memcpy(&(buffer[OFFSET_TREE_HEIGHT]), &treeHeight, sizeof(int));
	
	// Set the pid1, key and pid2
	memcpy(&(buffer[NON_LEAF_BYTES_RESERVED]), &pid1, sizeof(PageId));
	memcpy(&(buffer[NON_LEAF_BYTES_RESERVED+4]), &key, sizeof(int));
	memcpy(&(buffer[NON_LEAF_BYTES_RESERVED+8]), &pid2, sizeof(PageId));
	
	return 0;
}

void BTNonLeafNode::setParameters(int count, PageId rootPid, int treeHeight)
{
	//int leafCode = LEAF_CODE;
	//memcpy(&(buffer[0]), &leafCode, sizeof(int));
	if (count != -1)
	{
		int initKeyCount = 0;
		memcpy(&(buffer[OFFSET_KEY_COUNT]), &initKeyCount, sizeof(int));
	}
	memcpy(&(buffer[OFFSET_ROOT_PID]), &rootPid, sizeof(int));
	memcpy(&(buffer[OFFSET_TREE_HEIGHT]), &treeHeight, sizeof(int));
}
